#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : TopKFrequentElements.py
# @Time    : 2020/9/7 9:24
# @Description:
from typing import List
from collections import Counter


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        Given a non-empty array of integers, return the k most frequent elements.

        Example 1:
            Input: nums = [1,1,1,2,2,3], k = 2
            Output: [1,2]
        Example 2:
            Input: nums = [1], k = 1
            Output: [1]
        Note:
            - You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
            - Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
            - It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
            - You can return the answer in any order.

        :param nums:
        :param k:
        :return:
        """
        # cnt = Counter(nums)
        # tmp = sorted(cnt.items(), key=lambda x: x[1], reverse=True)
        # ans = []
        # for i in range(k):
        #     ans.append(tmp[i][0])
        # return ans
        return [i[0] for i in Counter(nums).most_common(k)]


if __name__ == '__main__':
    S = Solution()
    nums = [3, 0, 1, 0]
    # nums = [1]
    # nums = [1, 1, 1, 2, 2, 3]
    k = 1
    print(S.topKFrequent(nums, k))
    print('done')
